package com.test.daily.leetcode.y2022.m06.day0614.v12;

import java.util.LinkedList;

/**
 * @author Tom on 2022/6/14
 */
public class Solution {
    public static int countRange(int[] arr, int range){
        int N = arr.length;
        LinkedList<Integer> maxQ = new LinkedList<>();
        LinkedList<Integer> minQ = new LinkedList<>();
        int R = 0;
        int count= 0;
        for(int L = 0; L < N; L++){
            while(R <= N){
                while(maxQ.size()!= 0 && arr[maxQ.peekFirst()] <= arr[R]){
                    maxQ.pollLast();
                }
                maxQ.add(R);
                while(minQ.size() != 0 && arr[minQ.pollLast()] >= arr[R]){
                    minQ.pollLast();
                }
                minQ.add(R);
                if(arr[maxQ.peekFirst()] - arr[minQ.peekFirst()] > range){
                    break;
                } else {
                    R++;
                }
            }
            count += R - L;
            if(minQ.peekFirst() == L){
                minQ.pollFirst();
            }
            if(maxQ.pollFirst() == L){
                maxQ.pollFirst();
            }
        }
        return count;
    }
}
